package com.demo.java.OD401_450.OD433;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【信道分配(C&D卷-200分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146321640
 */
public class OdMain {

    static int max_user = 0; // 用于记录最大支持的用户数
    static int D = 30; // 每个用户所需资源的需求值

    public static void main(String[] args) {
        int R = 5; // 资源的数量
        // 资源数组，表示每种资源的数量
        int[] num = new int[]{10, 5, 0, 1, 3, 2};

        // numss 数组，表示每种资源对应的大小是 2 的指数幂
        int[] numss = new int[R + 1];

        // 初始化 numss 数组，每个元素值为 2 的 i 次方
        for (int i = 0; i < numss.length; i++) {
            numss[i] = (int) Math.pow(2, i);
        }

        // 调用递归函数，计算最大支持的用户数
        max_people(numss, num, 0, 5);

        // 输出最大支持的用户数
        System.out.println(max_user);
    }

    // 递归函数计算最大支持的用户数
    public static void max_people(int[] numss, int[] num, int sum, int len) {
        // 如果分配的资源总和已经满足一个用户的需求，则增加支持的用户数
        if (sum >= D) {
            max_user++;  // 满足一个用户的需求，最大用户数加 1
            return; // 退出递归
        }

        // 遍历资源数组，从当前资源长度开始向前遍历
        for (int i = len; i >= 0 && num[i] >= 0; ) {
            if (num[i] == 0) { // 如果当前资源的数量为 0，跳过
                i--;
                continue;
            }

            // 分配资源，将当前资源大小累加到 sum 中
            sum += numss[i];

            // 如果资源的总和没有超过需求值 D，继续递归分配资源
            if (sum < D) {
                num[i]--; // 给当前用户分配一个资源
                max_people(numss, num, sum, i); // 递归调用，继续分配资源给下一个用户
            } else {
                // 如果资源总和超过需求值 D，说明已经满足了一个用户的需求
                sum = 0; // 重新计数，开始为下一个用户分配资源
                num[i]--; // 给当前用户分配一个资源
                max_user++; // 更新支持的最大用户数
            }
        }
    }
}
